package tree;


public class BinaryFindTree {
	private TreeNode root;
	public BinaryFindTree(TreeNode root) {
		this.root = root;
	}
	//插入节点
	public boolean Insert(TreeNode x) {
		 TreeNode p = root;
		 TreeNode q = null;
		 //查找插入的位置
		 while(p != null) {
			 q = p;
			 if(x.val == p.val) {return false;}
			 if(x.val < p.val) {p = p.left;}
			 else {p = p.right;}
		 }
		 //找到的位置就是q
		 if(root == null) root = x;
		 else if (x.val < q.val) q.left = x;
		 else q.right = x;
		 return true; 
	}
	//递归查找
	public TreeNode Search(TreeNode x) {
		return Search(root, x);
	}
	public TreeNode Search(TreeNode b, TreeNode x) {
		if(b == null) return null;
		if(x.val == b.val) return b;
		if(x.val < b.val) return Search(b.left, x);
		return Search(b.right, x);
	}
	//迭代查找
	public TreeNode IterSearch(TreeNode x) {
		TreeNode t = root;
		while(t != null) {
			if(t.val == x.val) return t;
			if(x.val < t.val) t = t.left;
			else t = t.right;
		}
		return null;
	}
}
